/**
 * 基于数组来实现 最大堆 结构
 *      二叉堆 中 每一个节点都一定比它的左右孩子节点大
 *      二叉堆本质是一棵完全二叉树
 */
public class MaxHeep<T extends Comparable<T>> {

    private Array<T> array;

    public MaxHeep(int capacity){
        array = new Array<>(capacity);
    }

    public MaxHeep(){
        array = new Array<>();
    }

    //返回堆中的元素个数
    public int size(){
        return array.getSize();
    }

    //判断堆是否为空
    public boolean isEmpty(){
        return array.isEmpty();
    }

    //返回完全二叉树的数组中，一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        return (index - 1) / 2;
    }

    //返回完全二叉树的数组中，一个索引所表示的元素的左孩子节点的索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    //返回完全二叉树的数组中，一个索引所表示的元素的右孩子节点的索引
    private int rightChild(int index){
        return index * 2 + 2;
    }

    //向堆中插入元素
    /*
        1、添加进数组中
        2、sift up(调整堆中的元素，使其满足每个节点都要大于其左右孩子节点)
     */
    public void add(T t){
        array.addLast(t);
        //sift up
        siftUp(array.getSize() - 1);
    }

    //sift up(调整堆中的元素，使其满足每个节点都要大于其左右孩子节点)
    private void siftUp(int index){
        while (index >0 && array.get(parent(index)).compareTo(array.get(index)) < 0){
            //调整元素位置
            array.swap(index,parent(index));
            index = parent(index);
        }
    }

    //看堆中最大的元素
    public T findMax(){
        if(array.getSize()==0){
            throw new IllegalArgumentException("cannot find max when heep is empty ");
        }
        return array.get(0);
    }

    //取出堆中最大的元素
    public T extractMax(){

        T t = findMax();
        array.swap(0,size()-1);
        array.removeLast();
        siftDown(0);
        return t;
    }

    private void siftDown(int index){

        while (leftChild(index) < array.getSize()){
            int j = leftChild(index);
            if(rightChild(index) < array.getSize() &&
                        array.get(j+1).compareTo(array.get(j))>0){
                j = rightChild(index);
            }
            //此时，data[j]是leftChild 和 rightchild中的最大值

            if(array.get(index).compareTo(array.get(j))>=0){
                break;
            }

            array.swap(index,j);
            index = j;
        }
    }

}
